package leetcode;

import java.util.*;

public class Leetcode127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int n = beginWord.length();
        Set<String> s = new HashSet<String>(wordList);
        Queue<String> q = new LinkedList<String>();
        q.offer(beginWord);
        int step = 1;
        while(!q.isEmpty()){
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if(cur.equals(endWord)){
                    return step;
                }
                for(int j = 0;j<n;j++){
                    for(char k = 'a';k<='z';k++){
                        StringBuilder sb = new StringBuilder(cur);
                        sb.setCharAt(j,k);
                        String nextWord = sb.toString();
                        if(s.contains(nextWord)){
                            if(nextWord.equals(endWord)){
                                return step + 1;
                            }
                            q.offer(nextWord);
                            s.remove(nextWord);
                        }
                    }
                }

            }
            step++;
        }
        return 0;
    }
}
